package com.problem;

/**
 * https://leetcode-cn.com/problems/count-primes/
 */
public class CountPrimes {

    //质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
    //10   ,4, 2 3 5 7
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
//        int s = 1;
//
//        for (int i=3;i<n;i++) {
//
//            if (i%2==0){
//                continue;
//            }
//            boolean isPrimes =true;
//            for (int j=3;j<=Math.sqrt(i);j+=2) {
//
//
//                if (i% j == 0) {
//                    isPrimes = false;
//                    break;
//                }
//            }
//            if (isPrimes) {
//                s++;
//                //System.out.println(i);
//            }
//
//        }
//        return s;

        boolean[] nums = new boolean[n];
        for (int i=2;i<nums.length;i++) {
            nums[i]  =true;
        }
        for (int i=2;i*i<nums.length;i++) {
            if (nums[i]) {
                for (int j=i*i;j<nums.length;j+=i) {
                    nums[j] = false;
                }
            }
        }
        int res = 0;
        for (boolean b : nums) {
            res += b?1:0;
        }
        return res;
    }
}
